docs/Linear probing sort.htm

   1 <HEAD>
   2 <TITLE>Linear probing sort
   3 </TITLE>
   4 <BODY>
   5 <H2>
   6 <H3>
   7 <A HREF="../../images/handbook.gif"><IMG SRC="../../images/handbook2.gif" align=left></A>
   8 <A HREF="../../hbook.html">
   9 <IMG SRC="../../images/home_g.gif" hspace = 15 vspace = 4 ALT = "[Home]"></A><BR>
  10 <A HREF="../../sort_a.html">
  11 <IMG SRC="../../images/chapter_g.gif" hspace = 15 vspace = 4 ALT = "[Chapter]"></A><BR>
  12 <A HREF="../../expand.html">
  13 <IMG SRC="../../images/contents_g.gif" hspace = 15 vspace = 4 ALT = "[Contents]"></A><BR>
  14 <A HREF="417.sort.c.html">
  15 </A>
  16 <A HREF="417.sort.c.html">
  17 <IMG SRC="../../images/prevalg_g.gif" hspace = 15 vspace = 4 ALT = "[Previous Algorithm]"></A><BR>
  18 <A HREF="42.char.c.html">
  19 <IMG SRC="../../images/nextalg_g.gif" hspace = 15 vspace = 4 ALT = "[Next Algorithm]"></A><BR>
  20 <BR></H2>
  21 <HR>
  22 <H2><B>Linear probing sort
  23 </B></H2><BR>
  24 <CENTER>
  25 <TABLE BORDER>
  26 <TR>
  27 <TD COLSPAN = 1>
  28 <TD rowspan = 1>
  29 <TR><TD>
  30 <XMP>
  31      procedure sort( var r : ArrayToSort; lo, up : integer );
  32
  33      var  i, j : integer;
  34           r1 : ArrayToSort;
  35      begin
  36      r1 := r;
  37      for j:=lo to UppBoundr do r[j].k := NoKey;
  38      for j:=lo to up do begin
  39           i := phi(r1[j].k,lo,m);
  40           while r[i].k <> NoKey do begin
  41                if r1[j].k < r[i].k then begin
  42                     r1[j-1] := r[i];
  43                     r[i] := r1[j];
  44                     r1[j] := r1[j-1]
  45                     end;
  46                i := i+1;
  47                if i > UppBoundr then Error
  48                end;
  49           r[i] := r1[j]
  50           end;
  51      i := lo-1;
  52      for j:=lo to UppBoundr do
  53           if r[j].k <> NoKey then begin
  54                i := i+1;
  55                r[i] := r[j]
  56                end;
  57      for j:=i+1 to UppBoundr do    r[j].k := NoKey;
  58      end;
  59 </XMP></TD></TR></TABLE>
  60 <BR>
  61 <H3><A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/4/417.sort.c"><IMG SRC="../../images/ftp.xbm" hspace=10>C</A> source (417.sort.c)  <A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/4/417.sort.p"><IMG SRC="../../images/ftp.xbm" hspace=10>Pascal</A> source (417.sort.p)
  62 </H3></CENTER>
  63 <HR><H4>
  64 <IMG SRC="../../images/aw3.gif" align=left><H5><BR>
  65 &copy <A HREF="http://aw.com">Addison-Wesley </A>Publishing Co. Inc.
  66 </H5></H4><HR>
  67 </BODY>